public class MaxPathSum {
    // leetcode 二叉树中的最大路径和
    // https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/?envType=study-plan-v2&envId=top-100-liked
    /**
     * 对于当前节点，如何返回当前节点贡献的最大值呢
     * 当前节点可以作为最大路径和的根节点，也可以作为路径上的节点
     */
    private int maxSum = -1001;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return maxSum;
    }

    // 返回当前节点的最大贡献值
    private int dfs(TreeNode root) {
        if(root == null) return 0;

        int leftSum = Math.max(dfs(root.left), 0);
        int rightSum = Math.max(dfs(root.right), 0);
        // leftSum+rightSum+root.val记录经过当前节点的路径和
        maxSum = Math.max(maxSum, leftSum+rightSum+root.val);
        // 返回当前节点的最大贡献值
        return root.val + Math.max(leftSum, rightSum);
    }
}
